﻿#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <queue>
#include <stack>
using namespace std;

//1047. 删除字符串中的所有相邻重复项
//https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
class Solution {
public:
    string removeDuplicates(string s) {
        string ret;
        for (auto ch : s) {
            if (ret.size() && ret.back() == ch) {
                ret.pop_back();
            }
            else {
                ret += ch;
            }
        }
        return ret;
    }
};

//844. 比较含退格的字符串
//https://leetcode.cn/problems/backspace-string-compare/
class Solution {
public:
    bool backspaceCompare(string s, string t) { return judge(s) == judge(t); }
    string judge(string& s) {
        string ret;
        for (auto ch : s) {
            if (ch == '#') {
                if (ret.size())
                    ret.pop_back();
            }
            else {
                ret += ch;
            }
        }
        return ret;
    }
};

//227. 基本计算器 II
//https://leetcode.cn/problems/basic-calculator-ii/
class Solution {
public:
    int calculate(string s) {
        int n = s.size();
        vector<int> st;
        char op = '+';
        int i = 0;
        while (i < n) {
            if (s[i] == ' ')
                i++;
            else if (s[i] >= '0' && s[i] <= '9') {
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + (s[i++] - '0');

                if (op == '+')
                    st.push_back(tmp);
                else if (op == '-')
                    st.push_back(-tmp);
                else if (op == '*')
                    st.back() *= tmp;
                else
                    st.back() /= tmp;
            }
            else
                op = s[i++];
        }
        int sum = 0;
        for (auto n : st)
            sum += n;

        return sum;
    }
};


//394. 字符串解码
//https://leetcode.cn/problems/decode-string/
class Solution {
public:
    string decodeString(string s) {
        stack<string> st;
        stack<int> nums;
        st.push("");
        int i = 0, n = s.size();
        while (i < n) {
            if (s[i] >= '0' && s[i] <= '9') {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9') {
                    tmp = tmp * 10 + (s[i++] - '0');
                }
                nums.push(tmp);
            }
            else if (s[i] == '[') {
                string tmp = "";
                i++;// 把括号后⾯的字符串提取出来
                while (s[i] <= 'z' && s[i] >= 'a') {
                    tmp += s[i++];
                }
                st.push(tmp);
            }
            else if (s[i] == ']') {
                string tmp = st.top();
                st.pop();
                int n = nums.top();
                nums.pop();
                while (n--) {
                    st.top() += tmp;
                }
                i++;
            }
            else {
                while (i < n && s[i] >= 'a' && s[i] <= 'z') {
                    st.top() += s[i++];
                }
            }
        }
        return st.top();
    }
};


//946. 验证栈序列
//https://leetcode.cn/problems/validate-stack-sequences/
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int i = 0, n = popped.size();
        for (auto x : pushed) {
            st.push(x);
            while (st.size() && st.top() == popped[i]) {
                st.pop();
                i++;
            }
        }
        return i == n;
    }
};